package com.zjj.algorithm.learning.leetcode.sort;

import java.util.Arrays;
import java.util.IdentityHashMap;
import java.util.Map;

/**
 * 2418. 按身高排序 简单
 * 给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。
 *
 * 对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。
 *
 * 请按身高 降序 顺序返回对应的名字数组 names 。
 *
 * 示例 1：
 *
 * 输入：names = ["Mary","John","Emma"], heights = [180,165,170]
 * 输出：["Mary","Emma","John"]
 * 解释：Mary 最高，接着是 Emma 和 John 。
 * 示例 2：
 *
 * 输入：names = ["Alice","Bob","Bob"], heights = [155,185,150]
 * 输出：["Bob","Alice","Bob"]
 * 解释：第一个 Bob 最高，然后是 Alice 和第二个 Bob 。
 * @author zjj_admin
 * @date 2022/11/16 10:44
 */
public class SortThePeople {

    public static void main(String[] args) {

        String[] names = new String[]{"Mary","John","Emma","Mary","John","Emma","Mary","John","Emma"};
        int[] heights = new int[]{2,5,1,4,3,6,1,3,2};
        String[] people = sortPeople2(names, heights);
        System.out.println("people = " + Arrays.toString(people));
        System.out.println("heights = " + Arrays.toString(heights));

    }


    /**
     * 时间
     * 13 ms
     * 击败
     * 21.64%
     * 内存
     * 41.8 MB
     * 击败
     * 72.55%
     * @param names 姓名数组
     * @param heights 身高数组
     * @return
     */
    public static String[] sortPeople(String[] names, int[] heights) {
        int len = names.length;
        Map<String,Integer> map = new IdentityHashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(names[i], heights[i]);
        }
        Arrays.sort(names,(x1,x2) -> Integer.compare(map.get(x2),map.get(x1)));
        return names;
    }


    /**
     * 使用快速排序的方式解题
     * @param names
     * @param heights
     * @return
     */
    public static String[] sortPeople2(String[] names, int[] heights) {
        aesQuickSort(names,heights,0,names.length - 1);
        return names;
    }

    /**
     * 快速排序，通过 height 将两个数组一起排列，要求从大到小排序
     * names =   ["Alice","Bob","Bob"]
     * heights = [155,185,150]
     *      * 时间
     *      * 1 ms
     *      * 击败
     *      * 100%
     *      * 内存
     *      * 41.7 MB
     *      * 击败
     *      * 95.59%
     * @param names
     * @param heights
     * @param left
     * @param right
     */
    private static void desQuickSort(String[] names, int[] heights, int left, int right) {
        if(left >= right){
            return;
        }
        int l = left;
        int r = right;
        int pivot = heights[left];
        String pivotStr = names[left];
        while (l < r){
            //从右向左找，只要找到了一个值大于了最左边的 pivot
            while (l < r && heights[r] < pivot){
                r --;
            }
            if(l < r){
                //将右侧的比较大的值放到左边
                heights[l] = heights[r];
                //同步将names数据的数据同步修改
                names[l] = names[r];
                l ++;
            }

            //当 左边存在比 pivot 大的值就直接跳过
            while (l < r && heights[l] > pivot){
                l ++;
            }
            if(l < r){
                heights[r] = heights[l];
                names[r] = names[l];
                r --;
            }

        }
        heights[l] = pivot;
        names[l] = pivotStr;

        //继续向左递归调用
        desQuickSort(names,heights,left, l -1);
        //继续向右递归调用
        desQuickSort(names,heights,l + 1,right);

    }


    /**
     * 使用快速排序的方式，从小到大
     * @param names
     * @param heights
     * @param left
     * @param right
     */
    public static void aesQuickSort(String[] names, int[] heights, int left, int right) {
        if(left >= right){
            return;
        }
        int l = left;
        int r = right;
        //以最右边的数据为 pivot
        int pivot = heights[right];
        String pivotStr = names[right];
        while (l < r){
            //从左向右依次遍历，只要找到了比 pivot 大的数据就与 pivot 交换
            while (l < r && heights[l] < pivot){
                l ++;
            }
            //说明在 pivot 之前找到了一个比 pivot 大的值
            if(l < r){
                //此时的 pivot 为 heights[l]
                heights[r] = heights[l];
                names[r] = names[l];
                r --;
            }
            //从右向左依次遍历，当找到一个比 pivot 小的数据就和 pivot 交换
            while (l < r && heights[r] > pivot){
                r --;
            }

            //当找到了一个数据在比 pivot 小的时候，就交换
            if(l < r){
                heights[l] = heights[r];
                names[l] = names[r];
                l ++;
            }
        }
        heights[r] = pivot;
        names[r] = pivotStr;

        aesQuickSort(names,heights,left, l - 1);
        aesQuickSort(names,heights,l + 1,right);

    }


}
